import java.io.*;
import java.lang.Math;
class Node
{
	private Node next[];
	private int attributeNum;
	private String value;
	public boolean isLeaf;
	private boolean result;
	public static int sum = 0;
	public Node()
	{
		isLeaf = false;
		value = new String();
	}
	public Node getNext(int i)
	{
		return next[i];
	}
	public int getName()
	{
		return attributeNum;
	}
	private void setLeaf(boolean b)
	{
		isLeaf = true;
		result = b;
	}
	public boolean isLeaf()
	{
		return isLeaf;
	}
	public boolean getResult()
	{
		return result;
	}
	public void ID3(int setSize,int set[],boolean attributeSet[],int attributeSetNum,boolean b)
	{
		int i,j,k;
		int positive = 0,negative = 0;
		/**判断原集合中结果正负的多少*/
		for(i = 0;i < setSize;i++)
		{
			if(Attribute.getResult(set[i]))
				positive ++;
			else
				negative ++;
		}
		/**如果结果正负单一，则是叶子节点*/
		if(positive == 0)
		{
			setLeaf(false);
			sum = sum + 1;			
			return;
		}
		else if(negative == 0)
		{	
			setLeaf(true);
			sum = sum + 1;
			return;
		}
		/**如果属性列表为空，或者属性值为遗漏值，也为叶子节点*/
		else if(attributeSetNum == 0||value.equals("?"))
		{
			if(positive >= negative)
				setLeaf(true);
			else
				setLeaf(false);
			sum = sum + 1;				
			return;
		}
		/**否则，继续根据属性列表中的最优属性进行分裂*/
		else
		{
			if(positive >= negative)
				result = true;
			else
				result = false;
			isLeaf = false;
			int setTemp[] = new int[setSize];
			int setSizeTemp;
			boolean attributeSetTemp[] = new boolean[41];			
			/**取最优属性*/
			attributeNum = Attribute.getMaxGain(setSize,set,attributeSet);
			/**重新整理属性列表，为下一次做准备,如果下一次的属性个数为0，则无需整理*/
			if(attributeSetNum > 1)
			{
				for(i = 0;i < 41;i++)
					attributeSetTemp[i] = attributeSet[i];
				attributeSetTemp[attributeNum] = false;		
			}
			/**假如最优属性为非连续属性*/
			if(!Attribute.getIfContinuous(attributeNum))
			{
				next = new Node[Attribute.getNum(attributeNum) + 1];
				for(i = 0;i < Attribute.getNum(attributeNum) + 1;i++)
					next[i] = new Node();
				/**针对属性定义域的每个取值*/
				for(i = 0;i < Attribute.getNum(attributeNum);i++)
				{
					setSizeTemp = 0;
					/**针对集合中每个元素，判断元素属性取值是否与i一致*/
					for(j = 0;j < setSize;j++)
					{
						if(Attribute.getValue(set[j],attributeNum).equals(Attribute.getName(attributeNum,i)))
						{
							/**若一致，则整理子集合*/
							setTemp[setSizeTemp] = set[j];
							setSizeTemp++;
						}
					}
					/**ID3递归*/
					next[i].value = new String(Attribute.getName(attributeNum,i));
					next[i].ID3(setSizeTemp,setTemp,attributeSetTemp,attributeSetNum-1,b);
				}
				setSizeTemp = 0;
				for(i = 0;i < setSize;i++)
				{
					if((Attribute.getValue(set[i],attributeNum).equals("?")))					
					{		
						setTemp[setSizeTemp] = set[i];
						setSizeTemp++;
					}
				}
				next[Attribute.getNum(attributeNum)].value = new String("?");
				next[Attribute.getNum(attributeNum)].ID3(setSizeTemp,setTemp,attributeSetTemp,attributeSetNum-1,b);				
				return;				
			}
			/**若最优属性为连续属性*/			
			else
			{
				next = new Node[11];
				int setSizeArray[] = new int[10];
				int setArray[][] = new int[10][setSize];
				double t;
				for(i = 0;i < 11;i++)
					next[i] = new Node();
				/**对于集合中的每个元素*/
				for(i = 0;i < setSize;i++)
				{
					if(!(Attribute.getValue(set[i],attributeNum).equals("?")))
					{
						/**判断元素所在的区间*/
						t = (Double.parseDouble(Attribute.getValue(set[i],attributeNum)) - Attribute.getMinContinuous(attributeNum))/(Attribute.getMaxContinuous(attributeNum) - Attribute.getMinContinuous(attributeNum))*10;
						k = (new Double(t)).intValue();
						if(k == 10) k = 9;
						/**整理区间的子集合*/						
						setArray[k][setSizeArray[k]] = set[i];
						setSizeArray[k]++;	
					}
				}
				/**ID3递归*/
				for(i = 0;i < 10;i++)
					next[i].ID3(setSizeArray[i],setArray[i],attributeSetTemp,attributeSetNum-1,b);
				setSizeTemp = 0;
				for(i = 0;i < setSize;i++)
				{
					if((Attribute.getValue(set[i],attributeNum).equals("?")))					
					{		
						setTemp[setSizeTemp] = set[i];
						setSizeTemp++;
					}
				}
				next[10].value = new String("?");
				next[10].ID3(setSizeTemp,setTemp,attributeSetTemp,attributeSetNum-1,b);
				
				return;									
			}			
		}
	}
}
